public final class Hconstructiva extends Ejercicio
{ 
	public int[] Vo1, Vo2;
	public int cruces;
	
	protected Resultado DGIB
	(
			int n1, int v1[], int n2, int v2[], int m, Eje v1v2[],
			int np1, int vp1[], int np2, int vp2[], int mp, Eje vp1vp2[]
	){
		Resultado res = new Resultado();
		
		/*PRIMERA HEURISTICA CONSTRUCTIVA: 
		 Esta heuristica va eligiendo el mejor lugar para cada nodo
		 (para que genere la minima cantidad de cruces)...partiendo del
		 bipartito incremental*/
		
		int i; 
		int M = m + mp;
		int N1 = n1 + np1;
		int N2 = n2 + np2;
		Nodo[] IV1 = new Nodo[N1], IV2 = new Nodo[N2];
		Eje[] IV1V2 = new Eje[M];
		
		for( i = 0; i < n1; i++ )
			IV1[i] = new Nodo(v1[i],false);
		
		for( i = 0; i < np1; i++ )
			IV1[n1+i] = new Nodo(vp1[i],true);
		
		for( i = 0; i < n2; i++ )
			IV2[i] = new Nodo(v2[i],false);
		
		for( i = 0; i < np2; i++ )
			IV2[n2+i] = new Nodo(vp2[i],true);
		
		for( i = 0; i < m; i++ )
			IV1V2[i] = v1v2[i];
		
		for( i = 0; i < mp; i++ )
			IV1V2[m+i] = vp1vp2[i];
		
		//cruce maximo de ejes
		this.cruces = M*(M-1);
		//solucion optima
		this.Vo1 = new int[N1];
		this.Vo2 = new int[N2];
		
		constructiva
		(
			IV1, N1,
			IV2, N2,
			IV1V2, M
		);
		
		for( int l = 0; l < N1; l++ )
			this.Vo1[l] = IV1[l].valor;
		
		for(int l = 0; l < N2; l++ )
			this.Vo2[l] = IV2[l].valor;
		
		cruces = cantidadCruces(Vo1,N1,Vo2,N2,IV1V2,M);
		
		res.kid = cruces;
		res.n_iv1 = N1;
		res.iv1 = Vo1; 
		res.n_iv2 = N2;
		res.iv2 = Vo2;
		
		return res;
	}

	public void constructiva
	(
		Nodo[] IV1, int N1,
		Nodo[] IV2, int N2,
		Eje[] IV1V2, int M
	){		
		permutacionOptima(IV1, N1, IV2, N2, IV1V2, M, false);
		permutacionOptima(IV2, N2, IV1, N1, IV1V2, M, true);
	}
	
	private void permutacionOptima(
			Nodo Vmovil[], int Nmovil,
			Nodo Vfijo[], int Nfijo,
			Eje V1V2[], int M,
			boolean invertir
	){
		int i = 0, k, l, n, c=0, best_i = 0, best_c = M*(M-1);
		Nodo v;
		
		while( i < Nmovil )
		{
			if(Vmovil[i].incremental)
			{
				v = Vmovil[i];
				v.incremental = false;
				k = 0;
				n = i;
				
				best_c = M*(M-1);
				
				while( k < Nmovil )
				{	
					if(k == 0)
					{
						for( l = n; l > k; l-- )
						{
							swap(Vmovil, l,l-1);
						}
					}
					else
					{
						swap(Vmovil,n,k);
					}

					for(int j = 0; j < M; j++)
					{
						if( invertir )
						{
							if(V1V2[j].destino == v.valor)
							{
								c = CrucesDelEje(Vfijo, Nfijo, Vmovil, Nmovil, V1V2, M,V1V2[j]);
							}
						}
						else
						{
							if(V1V2[j].origen == v.valor)
							{
								c = CrucesDelEje(Vmovil, Nmovil, Vfijo, Nfijo, V1V2, M,V1V2[j]);
							}
						}
					}
					
					if(c < best_c)
					{
						best_i = k;
						best_c = c;
					}

					n = k;
					k++;
					if(best_i <= i)
					{
						i++;
					}
				}
				
				for( l = n; l > best_i; l-- )
				{
					swap(Vmovil, l,l-1);
				}
			}
			else
			{
				i++;
			}
		}
	}
}